//#define _CRT_SECURE_NO_WARNINGS 1
//class Solution {
//public:
//    int minCut(string s) {
//        int n = s.size();
//        vector<vector<bool>>dp(n + 1, vector<bool>(n + 1, true));
//
//        for (int len = 1; len <= n; len++) {
//            for (int l = 0; l + len - 1 < n; l++) {
//                int r = l + len - 1;
//                if (len == 1) {
//                    dp[l][r] = true;
//                    continue;
//                }
//
//                if (s[l] == s[r]) {
//                    dp[l][r] = dp[l + 1][r - 1];
//                }
//                else {
//                    dp[l][r] = false;
//                }
//            }
//        }
//
//        vector<int> f(n + 1, 1e9);
//        f[0] = 0;
//        for (int i = 1; i < n; i++) {
//            if (dp[0][i]) {
//                f[i] = 0;
//                continue;
//            }
//            for (int j = i; j > 0; j--) {
//                if (dp[j][i]) {
//                    f[i] = min(f[i], f[j - 1] + 1);
//                }
//            }
//        }
//        //for(int i=0;i<n;i++)cout<<f[i]<<endl;
//        return f[n - 1];
//    }
//};